package com.test.daily.leetcode.y2022.m07.day0714.v04;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/14 下午 03:15
 * @version: 1.0
 */
public class Solution {
    public static class HeapGreater<T>{
        public HashMap<T, Integer> hashMap;
        public ArrayList<T> heap;
        public Comparator<? super T> c;
        int heapSize;

        public HeapGreater(Comparator<? super T> c){
            this.c = c;
            this.hashMap = new HashMap<>();
            this.heap = new ArrayList<>();
            this.heapSize = 0;
        }

        public void swap(int i, int j){
            T o1 = heap.get(i);
            T o2 = heap.get(j);
            heap.set(i, o2);
            heap.set(j, o1);
            hashMap.put(o1, j);
            hashMap.put(o2, i);
        }
        public void heapInsert(int index){
            while(c.compare(heap.get(index), heap.get((index - 1)/2) )< 0){
                swap(index, (index-1)/2);
                index= (index-1)/2;
            }
        }
        public void heapify(int index){
            int left = index * 2 + 1;
            while(left < heapSize){
                int largest = left + 1 < heapSize && c.compare(heap.get(left),heap.get(left+1))< 0? left + 1: left;
                largest = c.compare(heap.get(index), heap.get(largest)) < 0 ? largest: index;
                if(largest == index){
                    break;
                }
                swap(largest, index);
                index = largest;
                left = index * 2+ 1;
            }
        }
        public void push(T value){
            heap.set(heapSize - 1, value);
            hashMap.put(value, heapSize-1);
            heapInsert(heapSize++);
        }
        public void pop(){
            T ans = heap.get(0);
            swap(0, heapSize-1);
            heap.remove(heapSize--);
            hashMap.remove(ans);
            heapify(0);
        }
        public void resign(T obj){
            int index = hashMap.get(obj);
            heapify(index);
            heapInsert(index);
        }
        public void remove(T target){
            T replace = heap.get(heapSize-1);
            int index = hashMap.get(target);
            hashMap.remove(target);
            heap.remove(heapSize --);
            if(target != replace){
                hashMap.put(replace, index);
                heap.set(index, replace);
                resign(replace);
            }
        }



    }
}
